% Author: Timothy Riley
% Class: CS3022 Programming Paradigms
% Professor: CDR Shaffer
% Prolog implementation to calculate the mean, median and mode of a list
% Reference: http://cs.union.edu/~striegnk/learn-prolog-now/html/node39.html
% Reference: http://kti.mff.cuni.cz/~bartak/prolog/sorting.html
% Reference: http://www.swi-prolog.org/pldoc/doc_for?object=section(2,'A.12',swi('/doc/Manual/lists.html'))
% Reference: http://www.cse.unsw.edu.au/~billw/prologdict.html

% Method to obtain the length of a list
% Reference: CDR Shaffer Notes
% Param 1: List of elements
% Param 2: Result holding the length of the list
list_length([],0).
list_length([H|T],X) :- list_length(T,Y), X is Y + 1.

% Method to obtain the sum of the list
% Reference: CDR Shaffer Notes
% Param 1: List of elements
% Param 2: Result holding the sum of the elements in the list
list_sum([],0).
list_sum([H|T],X) :- list_sum(T,Y), X is Y + H.

% Standard quick sort algorithm referenced from website above.
% Param 1: List to sort
% Param 2: Result holding the sorted list
quick_sort([],[]).
quick_sort([H|T],Sorted):- pivoting(H,T,L1,L2),quick_sort(L1,Sorted1),quick_sort(L2,Sorted2), append(Sorted1,[H|Sorted2],Sorted).

% Quick sort helper method to divide the elements around the pivot
pivoting(H,[],[],[]).
pivoting(H,[X|T],[X|L],G):-X=<H,pivoting(H,T,L,G).
pivoting(H,[X|T],L,[X|G]):-X>H,pivoting(H,T,L,G).

% Step 1: Sum the items in the list
% Step 2: Divide the sum by the length of the list
% Param 1: List to obtain the mean from
% Param 2: Result containing the mean
mean(L,X) :- list_sum(L,A), list_length(L,B), X is A/B.

% Step 1: Sort the list using quick sort
% Step 2: Determine if the list length is even or odd
% Step 3: If Odd
% Step 3a: Obtain the value directly in the middle
% Step 4: If Even
% Step 4a: Obtain the mean (avg) of the middle two values
% Param 1: List to obtain the median from
% Param 2: Result containing the median
median(L,X) :- quick_sort(L,SL), list_length(SL, E), I is (E // 2), H is (I - 1), M is mod(E,2), (M==1 -> nth0(I,SL,X) ; nth0(H,SL,M1), nth0(I,SL,M2), append([M1],[M2],M3), mean(M3,X)).

% Step 1: Convert the list to a set
% Step 2: Interate over the key values calling countKey passing the
%         list to determine how many times the key appears in the list ref Map.mapWithKey
% Step 3: Convert resulting map to list
% Step 4: Reverse the tuple values in the list (e.g. [(3,6),(2,7)] => [(6,3),(7,2)]
% Step 5: Sort the list using quick sort
% Step 6: Obtain the last item in the list
% Step 7: Obtain the second item in the tuple (aka: the mode)
% Param 1: List to obtain the mode from
% Param 2: Result containing the mode
mode(L,X) :- list_to_set(L,S), high_frequency(S,L,HF,HV), X is HV.

% Step 1: Initialize highest frequency and value to null
% Step 2: Calculate the number of times an item appears in the list
% Step 3: If highest frequency is null then
% Step 3a: Set the highest frequency and value to the first frequency and element returned
% Step 4: Else highest frequency is not null
% Step 4a: If the current frequency is greater than the highest then
% Step 4b: Set the highest frequency and value to the current setting
% Step 5: Else current frequency is not greater
% Step 5a Maintain highest frequency and value to their current settings
% Param 1: Unique set of elements in list
% Param 2: List of elements to search for the highest frequency
% Param 3: Highest frequency value in the list
% Param 4: Element associated with the highest frequency value
high_frequency([],[],null,null).
high_frequency([],L,null,null).
high_frequency([H|T],L,HF,HV) :- high_frequency(T,L,HG,HW),frequency(H,L,F),(HG == null -> HF is F, HV is H ; (F > HG -> HF is F, HV is H ; HF is HG, HV is HW)).

% Method to obtain the frequency an item appears in a list
% Param 1: Item to check the frequency of occurrences in the list
% Param 2: The list to use for frequency checks
% Param 3: The frequency of the item
frequency(X,[],0).
frequency(X,[H|T],F) :- frequency(X,T,G), (X==H -> F is (G + 1) ; F is G).

% Main method to obtain the mean median and mode of a list using the prolog languange
% Param 1: List of elements
% Param 2: Result containing the mean
% Param 3: Result containing the median
% Param 4: Result containing the mode
statistics([],null,null,null).
statistics(L, Mean, Median, Mode) :- mean(L,Mean), median(L,Median), mode(L,Mode).